package algorithm.tree;

/**
 * 构造二叉树查找树
 *
 * @author: fengpeng
 * @date: 2018/12/12  下午12:03
 */
public class BinarySearchTree<T extends Comparable<? super T>> {

    private BinaryNode<T> rootTree;


    /**
     * 向二叉查找树中插入数据
     *
     * @param t 要插入的节点数据
     */
    public void insert(T t) {
        rootTree = insert(t, rootTree);
    }

    /**
     * 向二叉查找树中插入数据
     *
     * @param t    要插入的节点数据
     * @param node 插入节点数据前的二叉树节点
     * @return 插入节点数据后的二叉树节点
     */
    private BinaryNode<T> insert(T t, BinaryNode<T> node) {
        if (node != null) {
            //如果原二叉树为空，则构造一个新的二叉树
            return new BinaryNode<T>(t, null, null);
        } else {
            //反之，则比较当前节点数据和要插入数据的大小，如果当前节点数据大，则插入到左子树，反之插入到右子树
            if (node.data.compareTo(t) > 0) {
                node.left = insert(t, node.left);
            } else {
                node.right = insert(t, node.right);
            }
            return node;
        }
    }

    /**
     * 判断数据T在二叉树中是否存在
     *
     * @param t 待查找的数据
     * @return
     */
    public boolean contains(T t) {
        return contains(t, rootTree);
    }

    /**
     * 判断数据T在二叉树中是否存在
     *
     * @param t 待查找的数据
     * @return
     */
    private boolean contains(T t, BinaryNode<T> rootTree) {
        if (rootTree == null) {
            return false;
        }
        int result = rootTree.data.compareTo(t);
        if (result > 0) {
            //如果当期结点大于待查找数据，则在左子树中寻找，
            // 反之，则在右子树中寻找，相等的话，则返回true
            contains(t, rootTree.left);
        } else if (result < 0) {
            contains(t, rootTree.right);
        }
        return true;
    }

    /**
     * 找最小值
     *
     * @return
     */
    public T  finMin(){
        if (rootTree == null ){
            return null;
        }
       return finMin(rootTree);
    }

    /**
     * 找最小值
     *
     * @param tree 二叉树
     * @return
     */
    private T finMin(BinaryNode<T> tree){
        if(tree.left == null ){
            return tree.data;
        }else{
            return finMin(tree.left);
        }
    }

    /**
     * 找最大值
     *
     * @return
     */
    public T finMax(){
        if (rootTree == null){
            return null;
        }
        return finMax(rootTree);
    }

    /**
     * 找最大值
     *
     * @param rootTree 二叉树
     * @return
     */
    private T finMax(BinaryNode<T> rootTree) {
        if (rootTree.right == null ){
            return  rootTree.data;
        }
        return finMax(rootTree.right);
    }




}
